home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / Python 1.3.3 / Python 133 SRC / Mac / mwerks / malloc / malloc.c < prev    next >
Text File  |  1995-08-31  |  11KB  |  416 lines
  1. /*
  2.  * Attempt at a memory allocator for the Mac, Jack Jansen, CWI, 1995.
  3.  *
  4.  * Code adapted from BSD malloc, which is:
  5.  *
  6.  * Copyright (c) 1983 Regents of the University of California.
  7.  * All rights reserved.
  8.  *
  9.  * Redistribution and use in source and binary forms, with or without
  10.  * modification, are permitted provided that the following conditions
  11.  * are met:
  12.  * 1. Redistributions of source code must retain the above copyright
  13.  *    notice, this list of conditions and the following disclaimer.
  14.  * 2. Redistributions in binary form must reproduce the above copyright
  15.  *    notice, this list of conditions and the following disclaimer in the
  16.  *    documentation and/or other materials provided with the distribution.
  17.  * 3. All advertising materials mentioning features or use of this software
  18.  *    must display the following acknowledgement:
  19.  *    This product includes software developed by the University of
  20.  *    California, Berkeley and its contributors.
  21.  * 4. Neither the name of the University nor the names of its contributors
  22.  *    may be used to endorse or promote products derived from this software
  23.  *    without specific prior written permission.
  24.  *
  25.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  26.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  27.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  29.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  30.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  31.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  32.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  33.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  34.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  35.  * SUCH DAMAGE.
  36.  */
  37.  
  38. #if defined(LIBC_SCCS) && !defined(lint)
  39. /*static char *sccsid = "from: @(#)malloc.c    5.11 (Berkeley) 2/23/91";*/
  40. static char *rcsid = "$Id: malloc.c,v 1.3 1995/08/31 13:51:13 jack Exp $";
  41. #endif /* LIBC_SCCS and not lint */
  42.  
  43. /*
  44.  * malloc.c (Caltech) 2/21/82
  45.  * Chris Kingsley, kingsley@cit-20. Modified by Jack Jansen, CWI.
  46.  *
  47.  * This is a very fast storage allocator.  It allocates blocks of a small 
  48.  * number of different sizes, and keeps free lists of each size.  Blocks that
  49.  * don't exactly fit are passed up to the next larger size.
  50.  *
  51.  * Blocks over a certain size are directly allocated by calling NewPtr.
  52.  * 
  53.  */
  54.  
  55.  
  56. #define DEBUG
  57. #define DEBUG2
  58. #define MSTATS
  59. #define RCHECK
  60.  
  61. typedef unsigned char u_char;
  62. typedef unsigned long u_long;
  63. typedef unsigned int u_int;
  64. typedef unsigned short u_short;
  65. typedef u_long caddr_t;
  66.  
  67. #include <Memory.h>
  68. #include <stdlib.h>
  69. #include <string.h>
  70.  
  71. #define    NULL 0
  72.  
  73. static void morecore();
  74.  
  75. /*
  76.  * The overhead on a block is at least 4 bytes.  When free, this space
  77.  * contains a pointer to the next free block, and the bottom two bits must
  78.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  79.  * byte is the size index.  The remaining bytes are for alignment.
  80.  * If range checking is enabled then a second word holds the size of the
  81.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  82.  * The order of elements is critical: ov_magic must overlay the low order
  83.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  84.  */
  85. union    overhead {
  86.     union    overhead *ov_next;    /* when free */
  87.     struct {
  88.         u_char    ovu_magic0;    /* magic number */
  89.         u_char    ovu_index;    /* bucket # */
  90.         u_char    ovu_unused;    /* unused */
  91.         u_char    ovu_magic1;    /* other magic number */
  92. #ifdef RCHECK
  93.         u_short    ovu_rmagic;    /* range magic number */
  94.         u_long    ovu_size;    /* actual block size */
  95. #endif
  96.     } ovu;
  97. #define    ov_magic0    ovu.ovu_magic0
  98. #define    ov_magic1    ovu.ovu_magic1
  99. #define    ov_index    ovu.ovu_index
  100. #define    ov_rmagic    ovu.ovu_rmagic
  101. #define    ov_size        ovu.ovu_size
  102. };
  103.  
  104. #define    MAGIC        0xef        /* magic # on accounting info */
  105. #define RMAGIC        0x5555        /* magic # on range info */
  106.  
  107. #ifdef RCHECK
  108. #define    RSLOP        sizeof (u_short)
  109. #else
  110. #define    RSLOP        0
  111. #endif
  112.  
  113. #define OVERHEAD (sizeof(union overhead) + RSLOP)
  114.  
  115. /*
  116.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  117.  * smallest allocatable block is 8 bytes.  The overhead information
  118.  * precedes the data area returned to the user.
  119.  */
  120. #define    NBUCKETS 11
  121. #define MAXMALLOC (1<<(NBUCKETS+2))
  122. static    union overhead *nextf[NBUCKETS];
  123.  
  124. #ifdef MSTATS
  125. /*
  126.  * nmalloc[i] is the difference between the number of mallocs and frees
  127.  * for a given block size.
  128.  */
  129. static    u_int nmalloc[NBUCKETS+1];
  130. #include <stdio.h>
  131. #endif
  132.  
  133. #if defined(DEBUG) || defined(RCHECK) || defined(DEBUG2)
  134. #define    ASSERT(p)   if (!(p)) botch(# p)
  135. #include <stdio.h>
  136. static
  137. botch(s)
  138.     char *s;
  139. {
  140.     fprintf(stderr, "\r\nmalloc assertion botched: %s\r\n", s);
  141.      (void) fflush(stderr);        /* just in case user buffered it */
  142.     abort();
  143. }
  144. #else
  145. #define    ASSERT(p)
  146. #endif
  147.  
  148. void *
  149. malloc(nbytes)
  150.     size_t nbytes;
  151. {
  152.       register union overhead *op;
  153.       register long bucket;
  154.     register unsigned amt;
  155.  
  156.     /*
  157.     ** First the simple case: we simple allocate big blocks directly
  158.     */
  159.     if ( nbytes + OVERHEAD >= MAXMALLOC ) {
  160.         op = (union overhead *)NewPtr(nbytes+OVERHEAD);
  161.         if ( op == NULL )
  162.             return NULL;
  163.         op->ov_magic0 = op->ov_magic1 = MAGIC;
  164.         op->ov_index = 0xff;
  165. #ifdef MSTATS
  166.           nmalloc[NBUCKETS]++;
  167. #endif
  168. #ifdef RCHECK
  169.         /*
  170.          * Record allocated size of block and
  171.          * bound space with magic numbers.
  172.          */
  173.         op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  174.         op->ov_rmagic = RMAGIC;
  175.           *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  176. #endif
  177.         return (void *)(op+1);
  178.     }
  179.     /*
  180.      * Convert amount of memory requested into closest block size
  181.      * stored in hash buckets which satisfies request.
  182.      * Account for space used per block for accounting.
  183.      */
  184. #ifndef RCHECK
  185.     amt = 8;    /* size of first bucket */
  186.     bucket = 0;
  187. #else
  188.     amt = 16;    /* size of first bucket */
  189.     bucket = 1;
  190. #endif
  191.     while (nbytes + OVERHEAD > amt) {
  192.         amt <<= 1;
  193.         if (amt == 0)
  194.             return (NULL);
  195.         bucket++;
  196.     }
  197. #ifdef DEBUG2
  198.     ASSERT( bucket < NBUCKETS );
  199. #endif
  200.     /*
  201.      * If nothing in hash bucket right now,
  202.      * request more memory from the system.
  203.      */
  204.       if ((op = nextf[bucket]) == NULL) {
  205.           morecore(bucket);
  206.           if ((op = nextf[bucket]) == NULL)
  207.               return (NULL);
  208.     }
  209.     /* remove from linked list */
  210.       nextf[bucket] = op->ov_next;
  211.     op->ov_magic0 = op->ov_magic1 = MAGIC;
  212.     op->ov_index = bucket;
  213. #ifdef MSTATS
  214.       nmalloc[bucket]++;
  215. #endif
  216. #ifdef RCHECK
  217.     /*
  218.      * Record allocated size of block and
  219.      * bound space with magic numbers.
  220.      */
  221.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  222.     op->ov_rmagic = RMAGIC;
  223.       *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  224. #endif
  225.       return ((char *)(op + 1));
  226. }
  227.  
  228. /*
  229.  * Allocate more memory to the indicated bucket.
  230.  */
  231. static void
  232. morecore(bucket)
  233.     int bucket;
  234. {
  235.       register union overhead *op;
  236.     register long sz;        /* size of desired block */
  237.       long amt;            /* amount to allocate */
  238.       int nblks;            /* how many blocks we get */
  239.  
  240.     /*
  241.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  242.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  243.      */
  244.     sz = 1 << (bucket + 3);
  245. #ifdef DEBUG2
  246.     ASSERT(sz > 0);
  247. #endif
  248.     amt = MAXMALLOC;
  249.     nblks = amt / sz;
  250. #ifdef DEBUG2
  251.     ASSERT(nblks*sz == amt);
  252. #endif
  253.     op = (union overhead *)NewPtr(amt);
  254.     /* no more room! */
  255.       if (op == NULL)
  256.           return;
  257.     /*
  258.      * Add new memory allocated to that on
  259.      * free list for this hash bucket.
  260.      */
  261.       nextf[bucket] = op;
  262.       while (--nblks > 0) {
  263.         op->ov_next = (union overhead *)((caddr_t)op + sz);
  264.         op = (union overhead *)((caddr_t)op + sz);
  265.       }
  266.       op->ov_next = (union overhead *)NULL;
  267. }
  268.  
  269. void
  270. free(cp)
  271.     void *cp;
  272. {   
  273.       register long size;
  274.     register union overhead *op;
  275.  
  276.       if (cp == NULL)
  277.           return;
  278.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  279. #ifdef DEBUG
  280.       ASSERT(op->ov_magic0 == MAGIC);        /* make sure it was in use */
  281.       ASSERT(op->ov_magic1 == MAGIC);
  282. #else
  283.     if (op->ov_magic0 != MAGIC || op->ov_magic1 != MAGIC)
  284.         return;                /* sanity */
  285. #endif
  286. #ifdef RCHECK
  287.       ASSERT(op->ov_rmagic == RMAGIC);
  288.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  289. #endif
  290.       size = op->ov_index;
  291.       if ( size == 0xff ) {
  292. #ifdef MSTATS
  293.         nmalloc[NBUCKETS]--;
  294. #endif
  295.           DisposPtr((Ptr)op);
  296.           return;
  297.       }
  298.       ASSERT(size < NBUCKETS);
  299.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  300.       nextf[size] = op;
  301. #ifdef MSTATS
  302.       nmalloc[size]--;
  303. #endif
  304. }
  305.  
  306. void *
  307. realloc(cp, nbytes)
  308.     void *cp; 
  309.     size_t nbytes;
  310. {   
  311.     int i;
  312.     union overhead *op;
  313.     int expensive;
  314.     u_long maxsize;
  315.  
  316.       if (cp == NULL)
  317.           return (malloc(nbytes));
  318.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  319. #ifdef DEBUG
  320.       ASSERT(op->ov_magic0 == MAGIC);        /* make sure it was in use */
  321.       ASSERT(op->ov_magic1 == MAGIC);
  322. #else
  323.     if (op->ov_magic0 != MAGIC || op->ov_magic1 != MAGIC)
  324.         return NULL;                /* sanity */
  325. #endif
  326. #ifdef RCHECK
  327.       ASSERT(op->ov_rmagic == RMAGIC);
  328.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  329. #endif
  330.     i = op->ov_index;
  331.     /*
  332.     ** First the malloc/copy cases
  333.     */
  334.     expensive = 0;
  335.     if ( i == 0xff ) {
  336.         /* Big block. See if it has to stay big */
  337.         if (nbytes+OVERHEAD > MAXMALLOC) {
  338.             /* Yup, try to resize it first */
  339.             SetPtrSize((Ptr)op, nbytes+OVERHEAD);
  340.             if ( MemError() == 0 ) {
  341. #ifdef RCHECK
  342.                 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  343.                 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  344. #endif
  345.                 return cp;
  346.             }
  347.             /* Nope, failed. Take the long way */
  348.         }
  349.         maxsize = GetPtrSize((Ptr)op);
  350.         expensive = 1;
  351.     } else {
  352.         maxsize = 1 << (i+3);
  353.         if ( nbytes + OVERHEAD > maxsize )
  354.             expensive = 1;
  355.         else if ( i > 0 && nbytes + OVERHEAD < (maxsize/2) )
  356.             expensive = 1;
  357.     }
  358.     if ( expensive ) {
  359.         void *newp;
  360.         
  361.         newp = malloc(nbytes);
  362.         if ( newp == NULL ) {
  363.             return NULL;
  364.         }
  365.         maxsize -= OVERHEAD;
  366.         if ( maxsize < nbytes )
  367.             nbytes = maxsize;
  368.         memcpy(newp, cp, nbytes);
  369.         free(cp);
  370.         return newp;
  371.     }
  372.     /*
  373.     ** Ok, we don't have to copy, it fits as-is
  374.     */
  375. #ifdef RCHECK
  376.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  377.     *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  378. #endif
  379.     return(cp);
  380. }
  381.  
  382.  
  383. #ifdef MSTATS
  384. /*
  385.  * mstats - print out statistics about malloc
  386.  * 
  387.  * Prints two lines of numbers, one showing the length of the free list
  388.  * for each size category, the second showing the number of mallocs -
  389.  * frees for each size category.
  390.  */
  391. mstats(s)
  392.     char *s;
  393. {
  394.       register int i, j;
  395.       register union overhead *p;
  396.       int totfree = 0,
  397.       totused = 0;
  398.  
  399.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  400.       for (i = 0; i < NBUCKETS; i++) {
  401.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  402.               ;
  403.           fprintf(stderr, " %d", j);
  404.           totfree += j * (1 << (i + 3));
  405.       }
  406.       fprintf(stderr, "\nused:\t");
  407.       for (i = 0; i < NBUCKETS; i++) {
  408.           fprintf(stderr, " %d", nmalloc[i]);
  409.           totused += nmalloc[i] * (1 << (i + 3));
  410.       }
  411.       fprintf(stderr, "\n\tTotal small in use: %d, total free: %d\n",
  412.         totused, totfree);
  413.     fprintf(stderr, "\n\tNumber of big (>%d) blocks in use: %d\n", MAXMALLOC, nmalloc[NBUCKETS]);
  414. }
  415. #endif
  416.